package cn.hughie.str;

/**
 * @author yuh
 * @date 2018/5/22 11:47
 * @description
 */
public class KMP2 {

    public static int[] getNext(String ptr) {
        int[] next = new int[ptr.length()];
        int k = -1;
        int i = 0;
        next[0] = -1;
        char[] chars = ptr.toCharArray();
        while (i < chars.length-1) {
            if (k == -1 || chars[i] == chars[k]) {
                i++;
                k++;
                if (chars[k] != chars[i]) {
                    next[i] = k;
                } else {
                    next[i] = next[k];
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }


    public static int kmp(String str, String ptr) {
        char[] ss = str.toCharArray();
        char[] ps = ptr.toCharArray();
        int[] next = getNext(ptr);
        int i = 0;
        int j = 0;
        while(i < ss.length && j < ps.length){
            if(j == -1 || ss[i] == ps[j]){
                i ++;
                j ++;
            }else{
                j = next[j];
            }
        }

        if(j == ptr.length()){
            return i-j;
        }else{
            return -1;
        }

    }

    public static void main(String[] args) {
        int kmp = kmp("acb", "c");
        System.out.println(kmp);
    }
}
